"""


贪心算法（Greedy Algorithm）是一种在每一步决策中都采取当前看来最优选择的算法策略，通过局部最优解的累积来试图获取全局最优解。它不回溯、不考虑未来步骤的影响，仅基于当前信息做出选择。
核心思想：
“贪心” 体现在只关注眼前的最大利益：
    每一步都选择对当前最有利的选项（局部最优）；
    不后悔之前的选择，也不预测未来的变化；
    最终通过一系列局部最优解，期望得到全局最优解。
适用场景：
贪心算法并非适用于所有问题，只有当问题满足以下两个条件时才能使用：
    贪心选择性质：局部最优选择能导致全局最优解（即不考虑过去的选择，仅当前最优就能累积出全局最优）。
    最优子结构：问题的全局最优解包含子问题的最优解。

经典案例：
1. 硬币找零问题（假设硬币面额为 [25, 10, 5, 1]）
目标：用最少的硬币凑出指定金额。贪心策略：每次优先选最大面额的硬币，直到金额凑完。例如，凑 30 元：1个25 +1个5, 累计需要2枚（最优解）。

2. 活动选择问题
目标：在多个有重叠时间的活动中，选择最多不重叠的活动。贪心策略：每次选结束时间最早的活动，剩余时间可容纳更多活动。

3. 区间覆盖问题
目标：用最少的区间覆盖所有目标点。贪心策略：每次选覆盖当前起点且延伸最远的区间。


贪心算法的优缺点：
优点：实现简单、效率高（通常是 O (n log n)，因常需排序），适合解决大规模问题。
缺点：无法保证全局最优解（很多问题不满足 “贪心选择性质”）。
例如，硬币面额为 [25, 10, 1] 时，凑 30 元用贪心（25+1×5）需6枚(这里解释下：当使用了1个25元，还需要凑5元，但是5<10，所以，只能找5个1元来凑了)，但最优解是 10×3（3 枚）。

代码示例（活动选择问题）：
def max_activities(activities):
    # 按活动结束时间排序（贪心选择的关键）
    activities.sort(key=lambda x: x[1])
    selected = [activities[0]]  # 选第一个结束的活动

    for act in activities[1:]:
        # 若当前活动开始时间 >= 上一个活动结束时间，则选择
        if act[0] >= selected[-1][1]:
            selected.append(act)

    return selected
# 活动格式：(开始时间, 结束时间)
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]
print(max_activities(activities))
# 输出：[(1,4), (5,7), (8,11), (12,16)]（4个不重叠活动，最优解）

总结：
贪心算法是一种 “短视” 但高效的策略，适用于满足特定条件的问题。使用时需先验证问题是否具备 “贪心选择性质” 和 “最优子结构”，否则可能得到次优解。在可行的场景下，它是解决问题的简洁高效方案。


再聚一个例子：
假设硬币面额为 [25, 10, 5, 1]（美元硬币面额），要你用最少的硬币数量凑足指定数量的金额
以 凑够87 分为例
    最大面额是 25 分：
    87 ÷ 25 = 3（个），剩余金额 = 87 - 3×25 = 12 分。
    下一个面额是 10 分：
    12 ÷ 10 = 1（个），剩余金额 = 12 - 1×10 = 2 分。
    下一个面额是 5 分：
    2 < 5，无法使用，跳过。
    最后一个面额是 1 分：
    2 ÷ 1 = 2（个），剩余金额 = 0，结束。

注意：贪心算法的局限性
如果硬币面额不满足 “贪心选择性质”，贪心算法可能会失效。例如：
若硬币面额为 [25, 10, 1]，目标金额 30 分：
贪心算法会选择 25 + 1×5（共 6 个硬币）(因为一个25后，还需要凑5元，但是5<10，所以，只能再找5个1元)，但最优解是 10×3（仅 3 个硬币）。
因此，使用贪心算法前需确保问题满足 “局部最优能累积成全局最优” 的条件。


"""